package com.huawei.M01.iterator.M02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
 *  s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
 * 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。
 * "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
 * 返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 *
 * @author 111
 */
public class FindSubstring {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        // 字符串总长度
        int length = words.length * words[0].length();
        List<String> wordList = Arrays.asList(words);
        for (int i = 0; i <= s.length() - length; i++) {
            if (isSonString(s, length, i, words[0].length(), new ArrayList<>(wordList))) {
                res.add(i);
            }
        }
        return res;
    }

    private boolean isSonString(String s, int length, int start, int subLength, List<String> wordList) {
        String model = s.substring(start, start + length);
        for (int i = 0; i < length; i += subLength) {
            if (!wordList.remove(model.substring(i, i + subLength))) {
                return false;
            }
        }
        return wordList.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(new FindSubstring().findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"}));
    }
}
